1. Field of the Invention
This invention relates to microprocessors and, more particularly, to register renaming mechanisms in microprocessors.
2. Description of the Related Art
Superscalar microprocessors achieve high performance by executing multiple instructions per clock cycle and by choosing the shortest possible clock cycle consistent with the design. As used herein, the term "clock cycle" refers to an interval of time accorded to various stages of an instruction processing pipeline within the microprocessor. Storage devices (e.g. registers and arrays) capture their values according to the clock cycle. For example, a storage device may capture a value according to a rising or falling edge of a clock signal defining the clock cycle. The storage device then stores the value until the subsequent rising or falling edge of the clock signal, respectively. The term "instruction processing pipeline" is used herein to refer to the logic circuits employed to process instructions in a pipelined fashion. Although the pipeline may be divided into any number of stages at which portions of instruction processing are performed, instruction processing generally comprises fetching the instruction, decoding the instruction, executing the instruction, and storing the execution results in the destination identified by the instruction.
Generally speaking, a given instruction has one or more source operands which are input values to be operated upon by the microprocessor in response to the given instruction. Each source operand is specified by the instruction via a source operand specifier. The source operand specifier defines a storage location which stores the corresponding source operand. In the x86 microprocessor architecture, for example, a source operand may be stored in a register or a memory location. Other microprocessor architectures specify that source operands are stored only in registers, except for load and store instructions which transfer values between registers and memory locations. Additionally, the given instruction typically has a destination operand. The destination operand is the result of the instruction. A destination operand is stored into a location specified by a destination operand specifier, which may specify a register or a memory location in the x86 microprocessor architecture and may be limited to registers only in certain other microprocessor architectures.
In order to locate a larger number of instructions which may be concurrently executed, superscalar microprocessors often employ out of order execution. If instructions are executed in order (i.e. "program order", or the order of instructions as listed in the program sequence being executed), then the number of instructions which may be concurrently executed is limited by dependencies between the instructions. A dependency exists between a first instruction and a second instruction if the second instruction receives a value produced via execution of the first instruction (the "result" of the first instruction) as a source operand. Since the second instruction needs the result of the first instruction prior to executing, the first and second instructions cannot be concurrently executed. However, an instruction subsequent to the second instruction which does not depend upon either the first instruction or the second instruction may be concurrently executed with the first instruction.
Unfortunately, out of order execution may generate "false dependencies". A false dependency exists between a first instruction and a second instruction subsequent to the first instruction if both instructions reference the same storage location and the first instruction must access the storage location prior to the second instruction in order for correct operation to occur. The second instruction writes the storage location in false dependency situations. False dependencies are divided into two types: write after write dependencies and write after read dependencies. A write after write dependency exists if both instructions write the same storage location. The first instruction must write the storage location first, and the second instruction write the storage location thereafter, such that the update made by the second instruction exists in the storage location subsequent to execution of the two instructions. Similarly, a write after read dependency exists if the first instruction reads the storage location and the second instruction writes the storage location. The read must be performed first so that the first instruction receives the value stored in the storage location prior to update in response to the second instruction.
A technique referred to as register renaming is often used to eliminate false dependencies in a microprocessor employing out of order execution. A microprocessor using register renaming typically has a larger implemented register set than architected register set. As used herein, a register is a storage device used to store the operands of instructions.
Source and destination register operand specifiers of an instruction identify one of a set of architected registers. Architected registers are defined by the microprocessor architecture employed by a given microprocessor. The number of architected registers is defined, as well as any special properties assigned to certain of the architected registers. The architected registers are the registers which can be specified by the programmer of an instruction sequence to store various values used by the instruction sequence.
On the other hand, the implemented register set comprises the registers actually implemented by the microprocessor. The number of implemented registers is at least equal to the number of architected registers, and is often substantially larger than the number of architected registers. As instructions are fetched and dispatched for execution, the destination operand of each instructions may be assigned to one of the implemented registers. In other words, the implemented register is "renamed" to be the destination architected register. Alternatively, the destination architected register can be considered to be renamed to the selected implemented register. The rename is maintained until a subsequent instruction overwrites the architected register, at which time another implemented register may be selected as the rename. Even though the same architected register may be updated by two instructions, different implemented registers are used to store the two destination operands. A particular instruction which reads the architected register being updated (i.e. uses the architected register's contents as a source operand) is directed to read the implemented register assigned to the first of the two instructions in program order if the particular instruction is between the two instructions in program order. A particular instruction subsequent to the second of the two instructions in program order is directed to read the implemented register assigned to the destination of the second of the two instructions. In this manner, false dependencies are eliminated by directing each update of a particular architected register to a different implemented register.
Unfortunately, register renaming complicates recovery from exceptions. Generally, an exception is a condition occurring upon execution of a particular instruction which causes instruction fetch and execution to transfer to a set of instructions not currently being fetched and executed by the microprocessor. For example, a branch misprediction is an exception. The instructions fetched beyond the mispredicted branch instruction are from an instruction stream other than the actual instruction stream being executed by the microprocessor. Therefore, these instructions must be discarded and instructions from the correct instruction stream fetched and executed. Similarly, an instruction may experience architecturally defined exceptions. For example, an instruction having a memory operand often specifies the memory operand via a virtual address which must be translated to a physical address of a main memory location via a predefined translation mechanism. If no translation is defined with the translation mechanism for the virtual address, an exception is generated for that instruction.
When previously fetched (and potentially executed) instructions are discarded due to an exception, the results which have been created by those instructions must be discarded as well. Essentially, the state of the architected registers must be restored to the state of these registers at the point in the program sequence at which the exception is detected. In the case of register renaming, this requirement translates to restoring the mapping of architected registers to implemented registers to a mapping consistent with the execution of instructions prior to the instruction experiencing the exception. Depending upon the type of exception, the instruction experiencing the exception may be executed or not executed. For example, a branch misprediction exception is an exception for which the corresponding branch instruction is executed. On the other hand, a failed virtual address translation for a memory operand of an instruction is an exception for which the corresponding instruction is not executed (the memory operand cannot be located, so the corresponding instruction cannot be executed). A method for restoring a register rename map to a state consistent with the execution of a particular instruction is therefore needed.